`:top
Fetching the instruction `F33f`_`[opcodes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Opcode]`_`f from program `F33f`_`[memory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_memory]`_`f well in advance is known as `F33f`_`[prefetching`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Instruction_prefetch]`_`f and it is served by using a `!prefetch input queue`! (PIQ). The pre-fetched instructions are stored in a `F33f`_`[queue`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=FIFO_(computing_and_electronics)]`_`f. The fetching of opcodes well in advance, prior to their need for execution, increases the overall efficiency of the `F33f`_`[processor`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Microprocessor]`_`f boosting its speed. The processor no longer has to wait for the memory access operations for the subsequent instruction opcode to complete. This architecture was prominently used in the `F33f`_`[Intel 8086 microprocessor`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Intel_8086]`_`f.
>>Contents
• `F0af`_`[Introduction`#introduction]`_`f
• `F0af`_`[Performance evaluation based on queuing theory`#performance-evaluation-based-on-queuing-theory]`_`f
• `F0af`_`[Instruction queue`#instruction-queue]`_`f
• `F0af`_`[Drawbacks`#drawbacks]`_`f
• `F0af`_`[x86 example code`#x86-example-code]`_`f
• `F0af`_`[Example program to detect size`#example-program-to-detect-size]`_`f
• `F0af`_`[See also`#see-also]`_`f
• `F0af`_`[References`#references]`_`f
• `F0af`_`[External links`#external-links]`_`f
-─
>>Introduction
`F33f`_`[Pipelining`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Pipeline_(computing)]`_`f was brought to the forefront of computing architecture design during the 1960s due to the need for faster and more efficient computing. Pipelining is the broader concept and most modern processors load their instructions some `F33f`_`[clock cycles`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Clock_cycle]`_`f before they execute them. This is achieved by pre-loading `F33f`_`[machine code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Machine_code]`_`f from memory into a `*prefetch input queue`*.
This behavior only applies to `F33f`_`[von Neumann computers`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Von_Neumann_computer]`_`f (that is, not `F33f`_`[Harvard architecture`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Harvard_architecture]`_`f computers) that can run `F33f`_`[self-modifying code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Self-modifying_code]`_`f and have some sort of `F33f`_`[instruction pipelining`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Instruction_pipelining]`_`f. Nearly all modern high-performance computers fulfill these three requirements.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]
Usually, the prefetching behavior of the PIQ is invisible to the `F33f`_`[programming model`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Programming_model]`_`f of the CPU. However, there are some circumstances where the behavior of PIQ is visible, and needs to be taken into account by the programmer.
When an `F33f`_`[x86`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=X86]`_`f processor changes mode from `F33f`_`[real mode`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Real_mode]`_`f to `F33f`_`[protected mode`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Protected_mode]`_`f and vice versa, the PIQ has to be flushed, or else the CPU will continue to translate the `F33f`_`[machine code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Machine_code]`_`f as if it were written in its last mode. If the PIQ is not flushed, the processor might translate its codes wrong and generate an invalid instruction `F33f`_`[exception`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Exception_handling]`_`f.
When executing `F33f`_`[self-modifying code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Self-modifying_code]`_`f, a change in the processor code immediately in front of the current location of execution might not change how the processor interprets the code, as it is already loaded into its PIQ. It simply executes its old copy already loaded in the PIQ instead of the new and altered version of the code in its `F33f`_`[RAM`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Random_access_memory]`_`f and/or `F33f`_`[cache`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=CPU_cache]`_`f.
This behavior of the PIQ can be used to determine if code is being executed inside an `F33f`_`[emulator`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Emulator]`_`f or directly on the hardware of a real CPU. Most emulators will `*probably`* never simulate this behavior. If the PIQ-size is zero (changes in the code `*always`* affect the state of the processor immediately), it can be deduced that either the code is being executed in an emulator or the processor invalidates the PIQ upon writes to addresses loaded in the PIQ.
>>Performance evaluation based on queuing theory
It was `F33f`_`[A.K Erlang`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Agner_Krarup_Erlang]`_`f (1878-1929) who first conceived of a queue as a solution to congestion in telephone traffic. Different `F33f`_`[queueing models`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Queueing_models]`_`f are proposed in order to approximately simulate the real time queuing systems so that those can be analysed mathematically for different performance specifications.
Queuing models can be represented using `F33f`_`[Kendall's notation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Kendall's_notation]`_`f:
A1/A2/A3/A4
where:
• A1 is the distribution of time between two arrivals
• A2 is the service time distribution
• A3 is the total number of servers
• A4 is the capacity of system
1. `!M/M/1 Model`! (Single Queue Single Server/ `F33f`_`[Markovian`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Markov_process]`_`f): In this model, elements of queue are served on a first-come, first-served basis. Given the mean arrival and service rates, then actual rates vary around these average values randomly and hence have to be determined using a `F33f`_`[cumulative probability distribution function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cumulative_distribution_function]`_`f.`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]
2. `!M/M/r Model`!: This model is a generalization of the basic M/M/1 model where multiple servers operate in parallel. This kind of model can also model scenarios with impatient users who leave the queue immediately if they are not receiving service. This can also be modeled using a `F33f`_`[Bernoulli process`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bernoulli_process]`_`f having only two states, success and failure. The best example of this model is our regular land-line telephone systems.`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f]
3. `!M/G/1 Model`! (Takacs' finite input Model) : This model is used to analyze advanced cases. Here the service time distribution is no longer a `F33f`_`[Markov process`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Markov_process]`_`f. This model considers the case of more than one failed machine being repaired by single repairman. Service time for any user is going to increase in this case.`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f]
Generally in applications like prefetch input queue, M/M/1 Model is popularly used because of limited use of queue features. In this model in accordance with microprocessors, the user takes the role of the execution unit and server is the bus interface unit.
>>Instruction queue
The processor executes a program by fetching the instructions from memory and executing them. Usually the processor execution speed is much faster than the memory access speed. Instruction queue is used to prefetch the next instructions in a separate buffer while the processor is executing the current instruction.
With a `F33f`_`[four stage pipeline`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Instruction_pipeline]`_`f, the rate at which instructions are executed can be up to four times that of sequential execution.`:cite-ref-5[`F5bf`_`[5`#cite-note-5]`_`f]
The processor usually has two separate units for fetching the instructions and for executing the instructions.`:cite-ref-6[`F5bf`_`[6`#cite-note-6]`_`f]`:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f]
The implementation of a `F33f`_`[pipeline`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Pipeline_(computing)]`_`f architecture is possible only if the bus interface unit and the execution unit are independent. While the execution unit is decoding or executing an instruction which does not require the use of the `F33f`_`[data`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=System_bus]`_`f and `F33f`_`[address buses`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Address_bus]`_`f, the bus interface unit fetches `F33f`_`[instruction opcodes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Opcode]`_`f from the memory.
This process is much faster than sending out an address, reading the opcode and then decoding and executing it. Fetching the next instruction while the current instruction is being decoded or executed is called pipelining.`:cite-ref-8[`F5bf`_`[8`#cite-note-8]`_`f]
The `F33f`_`[8086`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Intel_8086]`_`f processor has a six-byte prefetch instruction pipeline, while the `F33f`_`[8088`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Intel_8088]`_`f has a four-byte prefetch. As the Execution Unit is executing the current instruction, the bus interface unit reads up to six (or four) bytes of opcodes in advance from the memory. The queue lengths were chosen based on simulation studies.`:cite-ref-9[`F5bf`_`[9`#cite-note-9]`_`f]
An exception is encountered when the execution unit encounters a `F33f`_`[branch`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Branch_(computer_science)]`_`f instruction i.e. either a jump or a call instruction. In this case, the entire queue must be dumped and the contents pointed to by the instruction pointer must be fetched from memory.
>>Drawbacks
Processors implementing the instruction queue prefetch algorithm are rather technically advanced. The `F33f`_`[CPU design`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=CPU_design]`_`f level complexity of the such processors is much higher than for regular processors. This is primarily because of the need to implement two separate units, the `F33f`_`[BIU`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bus_(computing)]`_`f and `F33f`_`[EU`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Execution_unit]`_`f, operating separately.
As the complexity of these chips increases, the cost also increases. These processors are relatively costlier than their counterparts without the prefetch input queue.
However, these disadvantages are greatly offset by the improvement in processor execution time. After the introduction of prefetch instruction queue in the 8086 processor, all successive processors have incorporated this feature.
>>x86 example code
`B100`F9d9code_starts_here:`f`b
`B100`F9d9 mov bx, ahead`f`b
`B100`F9d9 mov word ptr cs:[bx], 9090h`f`b
`B100`F9d9ahead:`f`b
`B100`F9d9 jmp near to_the_end`f`b
`B100`F9d9 ; Some other code`f`b
`B100`F9d9to_the_end:`f`b
This `F33f`_`[self-modifying`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Self-modifying_code]`_`f program will overwrite the `*jmp to_the_end`* with two `F33f`_`[NOPs`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NOP_(code)]`_`f (which is encoded as `*0x9090`*). The jump `*jmp near to_the_end`* is assembled into two bytes of machine code, so the two NOPs will just overwrite this jump and nothing else. (That is, the jump is replaced with a do-nothing-code.)
Because the machine code of the jump is already read into the PIQ, and probably also already executed by the processor (`F33f`_`[superscalar`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Superscalar]`_`f processors execute several instructions at once, but they "pretend" that they don't because of the need for `F33f`_`[backward compatibility`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Backward_compatibility]`_`f), the change of the code will not have any change of the execution flow.
>>>Example program to detect size
This is an example `F33f`_`[NASM`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NASM_(computer_program)]`_`f-`F33f`_`[syntax`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Syntax]`_`f `F33f`_`[self-modifying`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Self-modifying_code]`_`f `F33f`_`[x86`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=X86]`_`f-`F33f`_`[assembly language`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Assembly_language]`_`f algorithm that determines the size of the PIQ:
`B100`F9d9code_starts_here:`f`b
`B100`F9d9 xor bx, bx ; zero register bx`f`b
`B100`F9d9 xor ax, ax ; zero register ax`f`b
`B100`F9d9`f`b
`B100`F9d9 mov dx, cs`f`b
`B100`F9d9 mov [code_segment], dx ; "calculate" codeseg in the far jump below (edx here too)`f`b
`B100`F9d9`f`b
`B100`F9d9around:`f`b
`B100`F9d9 cmp ax, 1 ; check if ax has been altered`f`b
`B100`F9d9 je found_size`f`b
`B100`F9d9 ; 0x90 = opcode "nop" (NO oPeration)`f`b
`B100`F9d9 mov byte [nop_field+bx], 0x90`f`b
`B100`F9d9 inc bx`f`b
`B100`F9d9`f`b
`B100`F9d9 db 0xEA ; 0xEA = opcode "far jump"`f`b
`B100`F9d9 dw flush_queue ; should be followed by offset (rm = "dw", pm = "dd")`f`b
`B100`F9d9code_segment:`f`b
`B100`F9d9 dw 0 ; and then the code segment (calculated above)`f`b
`B100`F9d9flush_queue:`f`b
`B100`F9d9 ; 0x40 = opcode "inc ax" (INCrease ax)`f`b
`B100`F9d9 mov byte [nop_field+bx], 0x40`f`b
`B100`F9d9nop_field:`f`b
`B100`F9d9 times 256 nop`f`b
`B100`F9d9 jmp around`f`b
`B100`F9d9found_size:`f`b
`B100`F9d9 ;`f`b
`B100`F9d9 ; register bx now contains the size of the PIQ`f`b
`B100`F9d9 ; this code is for [[real mode]] and [[16-bit protected mode]], but it could easily be changed into`f`b
`B100`F9d9 ; running for [[32-bit protected mode]] as well. just change the "dw" for`f`b
`B100`F9d9 ; the offset to "dd". you need also change dx to edx at the top as`f`b
`B100`F9d9 ; well. (dw and dx = 16 bit addressing, dd and edx = 32 bit addressing)`f`b
`B100`F9d9 ;`f`b
What this code does is basically that it changes the execution flow, and determines by `F33f`_`[brute force`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Brute-force_search]`_`f how large the PIQ is. "How far away do I have to change the code in front of me for it to affect me?" If it is too near (it is already in the PIQ) the update will not have any effect. If it is far enough, the change of the code will affect the program and the program has then found the size of the processor's PIQ. If this code is being executed under multitasking OS, the `F33f`_`[context switch`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Context_switch]`_`f may lead to the wrong value.
>>See also
• `F33f`_`[Sequence point`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Sequence_point]`_`f
>>References
`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f "ARM Information Center". `*ARM Technical Support Knowledge Articles`*.
`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `:citerefhayes1998`aHayes, John (1998). `*Computer Architecture and Organization`* (Second ed.). McGraw-Hill.
`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f `:citereffeller1968`aFeller, William (1968). `*An Introduction to Probability theory and its applications`* (Second ed.). John Wiley and Sons.
`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f `:citerefpapouliss-unnikrishna-pillai2008`aPapoulis, Athanasios; S.Unnikrishna Pillai (2008). `*Probability, Random Variables and Stochastic Processes`* (Fourth ed.). McGraw-Hill. pp. 784 to 800.
`:cite-note-5`!5.`! `F0af`_`[↑`#cite-ref-5]`_`f `:citerefzakyv-carl-hamacherzvonko-g-vranesic1996`aZaky, Safwat; V. Carl Hamacher; Zvonko G. Vranesic (1996). `*Computer Organization`* (Fourth ed.). McGraw-Hill. pp. 310–329. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0-07-114309-2.
`:cite-note-6`!6.`! `F0af`_`[↑`#cite-ref-6]`_`f "Block diagram of 8086 CPU".
`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f `:citerefhall2006`aHall, Douglas (2006). `*Microprocessors and Interfacing`*. Tata McGraw-Hill. p. 2.12. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0-07-060167-4.
`:cite-note-8`!8.`! `F0af`_`[↑`#cite-ref-8]`_`f `:citerefhall2006`aHall, Douglas (2006). `*Microprocessors and Interfacing`*. New Delhi: Tata McGraw-Hill. pp. 2.13 – 2.14. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0-07-060167-4.
`:cite-note-9`!9.`! `F0af`_`[↑`#cite-ref-9]`_`f `:citerefmckevittbayliss1979`aMcKevitt, James; Bayliss, John (March 1979). "New options from big chips". `*IEEE Spectrum`*. `!16`! (3): 28–34. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1109/MSPEC.1979.6367944. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 25154920.
>>External links
`c`F0af`_`[↑ Back to top`#top]`_`f`a